package everyday;

import java.util.Arrays;

public class T1187 {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        // 前i个数字，可操作j次的最小值
        int[][] record = new int[arr1.length + 1][arr1.length + 1];
        Arrays.fill(record[0], Integer.MIN_VALUE);
        for (int i = 1; i < record.length; i++) {
            for (int j = 0; j < record.length; j++) {
                if (j == 0) {
                    record[i][j] = arr1[i - 1] > record[i - 1][0] ? arr1[i - 1] : Integer.MAX_VALUE;
                } else {
                    record[i][j] = binFind(record[i - 1][j - 1], arr2);
                    if (record[i - 1][j] < arr1[i - 1]) {
                        record[i][j] = Math.min(record[i][j], arr1[i - 1]);
                    }
                }
            }
        }
        for (int i = 0; i < record.length; i++) {
            if (record[arr1.length][i] != Integer.MAX_VALUE) {
                return i;
            }
        }
        return -1;
    }

    // 寻找大于target的最小值
    private int binFind(int target, int[] nums) {
        int last = Integer.MAX_VALUE;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target) {
                last = nums[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return last;
    }
}
